export interface IComparer<T> {
    Compare(x: T, y: T): number;
}

export class SortedList<TKey, TValue> {

    private keys: TKey[] = [];
    private values: TValue[] = [];

    constructor(private comparer?: IComparer<TKey>) {
    }

    public Add(key: TKey, value: TValue): void {
        const index = this.keys.findIndex(k => this.comparer ? this.comparer.Compare(k, key) >= 0 : k === key);
        if (index !== -1) {
            throw new Error('An item with the same key has already been added.');
        }
        this.keys.splice(index + 1, 0, key);
        this.values.splice(index + 1, 0, value);
        if (!this.comparer) {
            this.Sort();
        }
    }

    public Remove(key: TKey): boolean {
        const index = this.keys.findIndex(k => k === key);
        if (index !== -1) {
            this.keys.splice(index, 1);
            this.values.splice(index, 1);
            return true;
        }
        return false;
    }

    public ContainsKey(key: TKey): boolean {
        return this.keys.some(k => k === key);
    }

    public GetValue(key: TKey): TValue | undefined {
        const index = this.keys.findIndex(k => k === key);
        if (index !== -1) {
            return this.values[index];
        }
        return undefined;
    }

    public TryGetValue(key: TKey, valueRef: { value?: TValue }): boolean {
        const index = this.keys.findIndex(k => k === key);
        if (index !== -1) {
            valueRef.value = this.values[index];
            return true;
        }
        valueRef.value = undefined;
        return false;
    }

    public ContainsValue(value: TValue): boolean {
        return this.values.includes(value);
    }

    public GetEnumerator(): IterableIterator<(TKey | TValue)[]> {
        return this.keys.map((key, index) => [key, this.values[index]])[Symbol.iterator]();
    }

    public IndexOfKey(key: TKey): number {
        return this.keys.findIndex(k => k === key);
    }

    public IndexOfValue(value: TValue): number {
        return this.values.indexOf(value);
    }

    public RemoveAt(index: number): void {
        if (index >= 0 && index < this.keys.length) {
            this.keys.splice(index, 1);
            this.values.splice(index, 1);
        } else {
            throw new Error('Index is out of range.');
        }
    }

    public Clear(): void {
        this.keys.length = 0;
        this.values.length = 0;
    }

    private Sort(): void {
        for (let i = 0; i < this.keys.length; i++) {
            let minIndex = i;
            for (let j = i + 1; j < this.keys.length; j++) {
                if (this.keys[j] < this.keys[minIndex]) {
                    minIndex = j
                }
            }
            [this.keys[i], this.values[i]] = [this.keys[minIndex], this.values[minIndex]]
        }
    }

}